package LC;

/**
 * https://leetcode.com/problems/min-stack/description/
 * Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
 * push(x) -- Push element x onto stack.
 * pop() -- Removes the element on top of the stack.
 * top() -- Get the top element.
 * getMin() -- Retrieve the minimum element in the stack.
 * Example:
 * MinStack minStack = new MinStack();
 * minStack.push(-2);
 * minStack.push(0);
 * minStack.push(-3);
 * minStack.getMin();   --> Returns -3.
 * minStack.pop();
 * minStack.top();      --> Returns 0.
 * minStack.getMin();   --> Returns -2.
 */
public class LC_155_MinStack_Design {
    public static void main(String[] args) {

    }

    static class MinStack {
        private final static int DEFAULT_SIZE = 1000;
        private int[] stack;
        private int[] minIndex;
        private int min = Integer.MAX_VALUE;
        private int index = -1;
        private int current = -1;

        public MinStack() {
            stack = new int[DEFAULT_SIZE];
            minIndex = new int[DEFAULT_SIZE];
        }

        public MinStack(int size) {
            stack = new int[size];
            minIndex = new int[size];
        }

        public void push(int x) {
            current++;
            if (current >= stack.length) {
                int[] tmp = new int[current * 2];
                System.arraycopy(stack, 0, tmp, 0, stack.length);
                stack = tmp;
                tmp = new int[current * 2];
                System.arraycopy(minIndex, 0, tmp, 0, minIndex.length);
                minIndex = tmp;
            }
            stack[current] = x;
            if (x < min) {
                min = x;
                index = current;
            }
            minIndex[current] = index;
        }

        public void pop() {
            current--;
            if (current >= 0) {
                min = stack[minIndex[current]];
                index = minIndex[current];
            }
        }

        public int top() {
            if (current < 0)
                throw new RuntimeException("No more data");
            return stack[current];
        }

        public int getMin() {
            if (current < 0)
                throw new RuntimeException("No more data");
            return stack[minIndex[current]];
        }
    }
}